package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangjy
 * @description 二叉搜索树的最小绝对差
 * @date 2025/4/24 14:27
 */
public class GetMinimumDifference_530 {


    // TODO 迭代法

    /**
     * 个解：先中序遍历，再求最小差值
     */
    public int getMinimumDifference2(TreeNode root) {
        if (root == null) return -1;

        List<Integer> vals = new ArrayList<>();
        preorder2(root, vals);

        int i = 0, j = 1, ans = Integer.MAX_VALUE;
        while (j < vals.size()) {
            int diff = vals.get(j) - vals.get(i);
            ans = Math.min(ans, diff);
            i++;
            j++;
        }
        return ans;
    }

    public void preorder2(TreeNode node, List<Integer> vals) {
        if (node == null) return;

        preorder2(node.left, vals);
        vals.add(node.val);
        preorder2(node.right, vals);
    }

    /**
     * 个解：dfs-递归-先序-双指针
     * <p>
     * 分析：
     * BST的中序遍历结果为严格递增数组，考虑对升序数组 a 求任意两个元素之差的绝对值的最小值，答案一定为相邻两个元素之差的最小值。
     */
    Integer ans = Integer.MAX_VALUE;

    TreeNode pre = null;

    public int getMinimumDifference(TreeNode root) {
        if (root == null) return ans;

        int left = getMinimumDifference(root.left);

        // pre不为空才求相邻节点的差值（相邻节点是指，中序遍历结果里相邻的节点）
        if (pre != null) {
            int cur = root.val - pre.val;
            if (cur < ans) ans = cur;
        }
        pre = root;

        int right = getMinimumDifference(root.right);

        return Math.min(left, right);
    }

}
